The statements in this section merely provide background information related to the present disclosure and may not constitute prior art.
As a guarantee to provide the quality of service that application programs need, Internet routers have to use input packets' header information to determine the class of the packet before offering appropriate services applicable to the respective classes. The task of classifying a packet into a correct one of the classes is called packet classification, which is carried out by mainly using source IP address, destination IP address, source port number, destination port number, protocol field, and such.
Such packet classification has difficulties for the reasons below.
First of all, multi-dimensional searching is essential to the packet classification as the method for search varies from field to another. The IP address fields require the operation of longest matching scheme when the port number fields require a range matching scheme and the protocol field should be subject to an exact matching process. The necessity of simultaneous execution of diverse searching schemes extracts a complexity of the searching operation which in turn lowers search speed.
Second, extra processes are required to identify all the matching rules throughout the search operations and also elect the highest priority one of the rules.
Third, all of these operations must be in wire-speed to meet the packet input speed.
Consequently, many researches are currently attempting to speed up the router processing of the packets. In particular, to cope with the difficulty of the multi-dimensional searches, methods have been suggested to deal with limited fields as opposed to the entire fields trying to improve the searching speed which is represented by the method of tuple space search algorithm.
TABLE 1Rule No.Source PrefixDestination PrefixTupleR01* 1*(1, 1)R11*110*(1, 3)R201*  00*(2, 2)R30*111*(1, 3)R4111* 110*(3, 3)R5010* 110*(3, 3)
Tuple space refers to a space due to combinations of lengths of the respective fields as exemplified by the rule set in Table 1 where rule R0 has a source prefix length of 1 and a destination prefix length of 1 and thus belongs to tuple (1, 1) and rule R1 has a source prefix length of 1 and a destination prefix length of 3 and thus belongs to tuple (1, 3).
If the tuple space is defined as in Table 1 by pairing the source prefix lengths with the destination prefix lengths, considering the lengths from 0 to 32 which a prefix may have, the number of tuples to make is 33×33=1089 at maximum. Therefore, with respective to each of the input packets in the router, it consumes much time to conduct a linear search on the entire tuples that possess at least one rule as was recognized by numerous studies to date of which the tuple pruning algorithm is most famous.
The tuple pruning algorithm attempts to improve the search performance by cutting down tuples unworthy of the search by using the search results of the individual fields. One-dimensional search is performed respectively for the source address field and the destination address field to get the result of information on matching prefix lengths, which are combined to form the tuples. In order to combine information of two field lengths, it is necessary to perform a cross-producting, which is a procedure to generate every possible number of tuple cases for the prefix lengths coinciding with the input after the respective field searches. However, because the resultant tuples of the cross-producting are combinations of the matching prefixes by the individual fields, it is susceptible to generate tuples that are not actually present in the rule set. Consequently, such tuples as being absent in the rule set are desired to be removed before deciding the object tuples to eventually search.
FIG. 1 is a diagram for illustrating conventional tuple pruning algorithm.
Such a typical algorithm has made a trie to perform a one-dimensional search against the rule set in Table 1 and stored the rules in a tuple space. The following description will be about the search procedure where the input packet's source address and the destination address are (0100, 1110) for an example.
The first step is to find every matching length by proceeding simultaneous individual searches on the source address field and the destination address field. The result of searching on the source address field is matches to 0*, 01*, and 010* and so the matching lengths are determined to be lengths 1, 2, and 3 while the destination address field has matches to 1* and 111* and then lengths 1 and 3 are determined as the matching lengths.
Cross-producting on the matching prefix length information from the one-dimensional search forms the total of six tuples including (1, 1), (1, 3), (2, 1), (2, 3), (3, 1), and (3, 3). By an incidental comparison with a previously stored tuple list, it is possible to remove those tuples that formed but not present in the rule set and they are tuples (2, 1), (2, 3), and (3, 1). Therefore, the surviving tuples are three including (1, 1), (1, 3), and (3, 3).
The search on the three tuples with respective to the input (0100, 1110) starts with a hashing-based search against tuple (1, 1) by applying as a hash key “01” that is a pair of a first bit of the first field with a first bit of the second field. Next comes a similar search against tuple (1, 3) for ‘0111’ and lastly against tuple (3, 3) for ‘010111’, thereby finding R3, which is the best matching rule (BMR). This field-by-field search with respect to given inputs would erase unworthy tuples of search, and hence improved the searching speed.
However, although the tuple pruning algorithm might have combinations of the prefix lengths available because they are there to determine the tuples, there were no ways to check the instances of the prefixes having distinct values. Of the filtered tuples (1, 1), (1, 3), and (3, 3) in this example, tuples (1, 1) and (3, 3) obviously accompanied the rules unmatched with the given input to cause the tuple searches in vain.
In other words, the tuple pruning algorithm holds an inherent drawback of low search performance because it gives rise to unnecessary tuple searching operations due to the tuple removals fully depending on the prefix length information.
In view of this problem, the present disclosure is to provide a method and apparatus for packet classification that performs a focused search on the probable tuples to match a rule set by using Bloom filter for filtering a tuple list generated based on information on field length matches.